package 代码随想录.栈与队列;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class _3有效的括号 {
    /**
     * 20. 有效的括号
     * https://leetcode.cn/problems/valid-parentheses/
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     * 有效字符串需满足：
     *      左括号必须用相同类型的右括号闭合。
     *      左括号必须以正确的顺序闭合。
     *      每个右括号都有一个对应的相同类型的左括号。
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack();
        for(int i=0;i<s.length();i++){
            switch(s.charAt(i)){
                case '(':
                case '{':
                case '[':
                    stack.push(s.charAt(i));
                    break;
                case ')':
                    if(stack.isEmpty())
                        return false;
                    if(stack.pop() != '(' ){
                        return false;
                    }
                    break;
                case '}':
                    if(stack.isEmpty())
                        return false;
                    if(stack.pop() != '{' ){
                        return false;
                    }
                    break;
                case ']':
                    if(stack.isEmpty())
                        return false;
                    if(stack.pop() != '[' ){
                        return false;
                    }
                    break;
            }
        }
        if(!stack.isEmpty()){
            return false;
        }
        return true;
    }

    public boolean isValid2(String s) {
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            //碰到左括号，就把相应的右括号入栈
            if (ch == '(') {
                deque.push(')');
            }else if (ch == '{') {
                deque.push('}');
            }else if (ch == '[') {
                deque.push(']');
            } else if (deque.isEmpty() || deque.peek() != ch) {
                return false;
            }else {//如果是右括号判断是否和栈顶元素匹配
                deque.pop();
            }
        }
        //最后判断栈中元素是否匹配
        return deque.isEmpty();
    }
}
